package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/7 13:18
 * @DESCRIPTION
 */
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
// 输入：nums = [1,2,3]
// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
public class 全排列 {
    LinkedList<Integer> path=new LinkedList<>();//路径
    List<List<Integer>> res=new ArrayList<>();//最终结果
    //方法一 自己写出
    //让每一个分支都有一个set集合来筛选掉已经用过的元素
    //但是仔细想一下这个递归的执行情况  把递归的情况在抽象树上模拟
    //为什么一个path数组就能返回所有的结果呢？
    //一样的道理，根本不需要每一个分支都保持一个新的set去筛选
    public List<List<Integer>> method1(int[] nums) {
        recursion(new HashSet<Integer>(),nums);
        return res;
    }
    public void recursion(HashSet<Integer>set,int[]nums){
        if(set.size()>=nums.length){
            res.add(new ArrayList<>(path));
        }

        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            recursion(new HashSet<Integer>(set),nums);
            set.remove(nums[i]);
            path.removeLast();
        }
    }

    //看了代码随想录
    //利用数组used来筛选掉已经用过的元素
    boolean[]used;
    public List<List<Integer>> method2(int[] nums) {
        used=new boolean[nums.length];//boolean 类型的变量默认初始值是 false
        recursion2(nums);
        return res;
    }
    public void recursion2(int[]nums){
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            recursion2(nums);
            used[i]=false;
            path.removeLast();
        }
    }


    public List<List<Integer>> practice(int[] nums) {
        used=new boolean[nums.length];
        recursionPractice(nums);
        return res;
    }

    public void recursionPractice(int[] nums){
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            recursionPractice(nums);
            used[i]=false;
            path.removeLast();
        }
    }

    public List<List<Integer>> practice2(int[] nums) {
        used=new boolean[nums.length];
        recursionPractice2(nums);
        return res;
    }

    public void recursionPractice2(int[]nums){
        if(path.size()>=nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]){
                continue;
            }
            path.add(nums[i]);
            used[i]=true;
            recursionPractice2(nums);
            used[i]=false;
            path.removeLast();
        }
    }
}
